Search Results

Documents authored by Sobocinski, Pawel

Document
DOI: 10.4230/LIPIcs.CONCUR.2019.37
Bialgebraic Semantics for String Diagrams

Authors: Filippo Bonchi, Robin Piedeleu, Pawel Sobocinski, and Fabio Zanasi

Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)

Abstract
Turi and Plotkin’s bialgebraic semantics is an abstract approach to specifying the operational semantics of a system, by means of a distributive law between its syntax (encoded as a monad) and its dynamics (an endofunctor). This setup is instrumental in showing that a semantic specification (a coalgebra) satisfies desirable properties: in particular, that it is compositional. In this work, we use the bialgebraic approach to derive well-behaved structural operational semantics of string diagrams, a graphical syntax that is increasingly used in the study of interacting systems across different disciplines. Our analysis relies on representing the two-dimensional operations underlying string diagrams in various categories as a monad, and their bialgebraic semantics in terms of a distributive law for that monad. As a proof of concept, we provide bialgebraic compositional semantics for a versatile string diagrammatic language which has been used to model both signal flow graphs (control theory) and Petri nets (concurrency theory). Moreover, our approach reveals a correspondence between two different interpretations of the Frobenius equations on string diagrams and two synchronisation mechanisms for processes, à la Hoare and à la Milner.
Cite as

Filippo Bonchi, Robin Piedeleu, Pawel Sobocinski, and Fabio Zanasi. Bialgebraic Semantics for String Diagrams. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.CONCUR.2019.37,
  author =	{Bonchi, Filippo and Piedeleu, Robin and Sobocinski, Pawel and Zanasi, Fabio},
  title =	{{Bialgebraic Semantics for String Diagrams}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{37:1--37:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Fokkink, Wan and van Glabbeek, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.37},
  URN =		{urn:nbn:de:0030-drops-109398},
  doi =		{10.4230/LIPIcs.CONCUR.2019.37},
  annote =	{Keywords: String Diagram, Structural Operational Semantics, Bialgebraic semantics}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.11
Rule Algebras for Adhesive Categories

Authors: Nicolas Behr and Pawel Sobocinski

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Abstract
We show that every adhesive category gives rise to an associative algebra of rewriting rules induced by the notion of double-pushout (DPO) rewriting and the associated notion of concurrent production. In contrast to the original formulation of rule algebras in terms of relations between (a concrete notion of) graphs, here we work in an abstract categorical setting. Doing this, we extend the classical concurrency theorem of DPO rewriting and show that the composition of DPO rules along abstract dependency relations is, in a natural sense, an associative operation. If in addition the adhesive category possesses a strict initial object, the resulting rule algebra is also unital. We demonstrate that in this setting the canonical representation of the rule algebras is obtainable, which opens the possibility of applying the concept to define and compute the evolution of statistical moments of observables in stochastic DPO rewriting systems.
Cite as

Nicolas Behr and Pawel Sobocinski. Rule Algebras for Adhesive Categories. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{behr_et_al:LIPIcs.CSL.2018.11,
  author =	{Behr, Nicolas and Sobocinski, Pawel},
  title =	{{Rule Algebras for Adhesive Categories}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.11},
  URN =		{urn:nbn:de:0030-drops-96781},
  doi =		{10.4230/LIPIcs.CSL.2018.11},
  annote =	{Keywords: Adhesive categories, rule algebras, Double Pushout (DPO) rewriting}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.13
Graphical Conjunctive Queries

Authors: Filippo Bonchi, Jens Seeber, and Pawel Sobocinski

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Abstract
The Calculus of Conjunctive Queries (CCQ) has foundational status in database theory. A celebrated theorem of Chandra and Merlin states that CCQ query inclusion is decidable. Its proof transforms logical formulas to graphs: each query has a natural model - a kind of graph - and query inclusion reduces to the existence of a graph homomorphism between natural models. We introduce the diagrammatic language Graphical Conjunctive Queries (GCQ) and show that it has the same expressivity as CCQ. GCQ terms are string diagrams, and their algebraic structure allows us to derive a sound and complete axiomatisation of query inclusion, which turns out to be exactly Carboni and Walters' notion of cartesian bicategory of relations. Our completeness proof exploits the combinatorial nature of string diagrams as (certain cospans of) hypergraphs: Chandra and Merlin's insights inspire a theorem that relates such cospans with spans. Completeness and decidability of the (in)equational theory of GCQ follow as a corollary. Categorically speaking, our contribution is a model-theoretic completeness theorem of free cartesian bicategories (on a relational signature) for the category of sets and relations.
Cite as

Filippo Bonchi, Jens Seeber, and Pawel Sobocinski. Graphical Conjunctive Queries. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.CSL.2018.13,
  author =	{Bonchi, Filippo and Seeber, Jens and Sobocinski, Pawel},
  title =	{{Graphical Conjunctive Queries}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{13:1--13:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.13},
  URN =		{urn:nbn:de:0030-drops-96805},
  doi =		{10.4230/LIPIcs.CSL.2018.13},
  annote =	{Keywords: conjunctive query inclusion, string diagrams, cartesian bicategories}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2017.24
Refinement for Signal Flow Graphs

Authors: Filippo Bonchi, Joshua Holland, Dusko Pavlovic, and Pawel Sobocinski

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract
The symmetric monoidal theory of Interacting Hopf Algebras provides a sound and complete axiomatisation for linear relations over a given field. As is the case for ordinary relations, linear relations have a natural order that coincides with inclusion. In this paper, we give a presentation for this ordering by extending the theory of Interacting Hopf Algebras with a single additional inequation. We show that the extended theory gives rise to an abelian bicategory—a concept due to Carboni and Walters—and highlight similarities with the algebra of relations. Most importantly, the ordering leads to a well-behaved notion of refinement for signal flow graphs.
Cite as

Filippo Bonchi, Joshua Holland, Dusko Pavlovic, and Pawel Sobocinski. Refinement for Signal Flow Graphs. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.CONCUR.2017.24,
  author =	{Bonchi, Filippo and Holland, Joshua and Pavlovic, Dusko and Sobocinski, Pawel},
  title =	{{Refinement for Signal Flow Graphs}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.24},
  URN =		{urn:nbn:de:0030-drops-77758},
  doi =		{10.4230/LIPIcs.CONCUR.2017.24},
  annote =	{Keywords: Signal flow graphs, refinement, operational semantics, string diagrams, symmetric monoidal inequality theory}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.CALCO.2015
LIPIcs, Volume 35, CALCO'15, Complete Volume

Authors: Lawrence S. Moss and Pawel Sobocinski

Published in: LIPIcs, Volume 35, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)

Abstract
LIPIcs, Volume 35, CALCO'15, Complete Volume
Cite as

6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Proceedings{moss_et_al:LIPIcs.CALCO.2015,
  title =	{{LIPIcs, Volume 35, CALCO'15, Complete Volume}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-84-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{35},
  editor =	{Moss, Lawrence S. and Sobocinski, Pawel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2015},
  URN =		{urn:nbn:de:0030-drops-55622},
  doi =		{10.4230/LIPIcs.CALCO.2015},
  annote =	{Keywords: Theory of Computation, Logics and Meanings of Programs, Semantics of Programming Languages}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.CALCO.2015.i
Front Matter, Table of Contents, Preface, List of Authors

Authors: Lawrence S. Moss and Pawel Sobocinski

Published in: LIPIcs, Volume 35, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)

Abstract
Front Matter, Table of Contents, Preface, List of Authors
Cite as

6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. i-xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{moss_et_al:LIPIcs.CALCO.2015.i,
  author =	{Moss, Lawrence S. and Sobocinski, Pawel},
  title =	{{Front Matter, Table of Contents, Preface, List of Authors}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  pages =	{i--xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-84-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{35},
  editor =	{Moss, Lawrence S. and Sobocinski, Pawel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2015.i},
  URN =		{urn:nbn:de:0030-drops-55225},
  doi =		{10.4230/LIPIcs.CALCO.2015.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, List of Authors}
}
Document
DOI: 10.4230/DagSemProc.04241.2
Summary 1: Adhesivity, Bigraphs and Bisimulation Congruences

Authors: Pawel Sobocinski

Published in: Dagstuhl Seminar Proceedings, Volume 4241, Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems (2005)

Abstract
This paper is intended as a short informal summary of some of the topics which arose at the Dagstuhl meeting held 6/06/04-11/06/04. In particular, we shall summarise some of the content of talks by H. Ehrig, F. Gadducci, O. H. Jensen, R. Milner, B. K�¶nig, V. Sassone and the author. The general areas include adhesive categories and generalisations, contextual labelled transition semantics for graph transformation systems via borrowed-contexts and GIPOs, and bigraphs. We shall conclude with a summary of some of the discussions which followed the aforementioned presentations.
Cite as

Pawel Sobocinski. Summary 1: Adhesivity, Bigraphs and Bisimulation Congruences. In Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems. Dagstuhl Seminar Proceedings, Volume 4241, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{sobocinski:DagSemProc.04241.2,
  author =	{Sobocinski, Pawel},
  title =	{{Summary 1: Adhesivity, Bigraphs and Bisimulation Congruences}},
  booktitle =	{Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4241},
  editor =	{Barbara K\"{o}nig and Ugo Montanari and Philippa Gardner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04241.2},
  URN =		{urn:nbn:de:0030-drops-286},
  doi =		{10.4230/DagSemProc.04241.2},
  annote =	{Keywords: graph transformation , category theory , bisimulation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact